package leetcode.editor.cn;

//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 
//
// 
//
// 注意： 
//
// 
// 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 
// 如果 s 中存在这样的子串，我们保证它是唯一的答案。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
// 
//
// 示例 2： 
//
// 
//输入：s = "a", t = "a"
//输出："a"
// 
//
// 示例 3: 
//
// 
//输入: s = "a", t = "aa"
//输出: ""
//解释: t 中两个字符 'a' 均应包含在 s 的子串中，
//因此没有符合条件的子字符串，返回空字符串。 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length, t.length <= 10⁵ 
// s 和 t 由英文字母组成 
// 
//
// 
//进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？ Related Topics 哈希表 字符串 滑动窗口 👍 1842 👎 0

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

//Java：【76】 - 最小覆盖子串
public class MinimumWindowSubstring_76{
    public static void main(String[] args) {
        Solution solution = new MinimumWindowSubstring_76().new Solution();
                // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String minWindow(String s, String t) {
        int len1=s.length(), len2 =t.length();
        if(len1<len2) return "";
        int[] count = new int[58];
        boolean[] need = new boolean[58];
        int needsCount=len2;
        for (int i = 0; i < len2; i++) {
            int ch = t.charAt(i)-'A';
            count[ch]++;
            need[ch] = true;
        }
        int l=-1, r=len1;
        Deque<Integer> indexs = new LinkedList<>();
        for (int i = 0; i < len1; i++) {
            int ch = s.charAt(i)-'A';
            if(need[ch])
                indexs.addLast(i); //将需要的字母下标进行入栈
            if(needsCount>0){ // 还有缺的字母
                if (need[ch]){
                    if(count[ch] >0){
                        needsCount--;
                    }
                    count[ch]--;
                }
            }else{ // 字母都齐了，对多余的反向累加
                if (need[ch]){
                    count[ch]--;
                }
            }
//            System.out.println(indexs);
            if(needsCount==0){
                // 处理栈首，去掉多余的字母 （不处理栈尾，因为是刚加的，可能多余的是在中间）
                while (count[s.charAt(indexs.getFirst())-'A']<0){
                    count[s.charAt(indexs.getFirst())-'A']++;
                    indexs.removeFirst();
                }
                if(indexs.getLast()-indexs.getFirst() < r-l){
                    l = indexs.getFirst();
                    r= indexs.getLast();
                }

            }
//            System.out.println(l+" "+r);
        }
//        System.out.println(needsCount);
//        System.out.println(Arrays.toString(count));
//        System.out.println(indexs);
        if(needsCount>0) return "";
        // 处理栈尾，去掉多余的字母（主要是最后一个可能是多余的）
        while (!indexs.isEmpty() && count[s.charAt(indexs.getLast())-'A']<0){
            count[s.charAt(indexs.getLast())-'A']++;
            indexs.removeLast();
        }
        if(indexs.getLast()-indexs.getFirst() < r-l){
            l = indexs.getFirst();
            r= indexs.getLast();
        }
        return s.substring(l, r+1);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
